package com.cplexValue;


import java.text.DecimalFormat;
import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

    public class Simplex_Method extends Simplex_Method_Data{
        static {
            System.out.println("==================单纯形法求解线性规划=================");
        }

        /**
         * 主方法
         */
        public static void main( String[] args  ) throws Exception {
            String filePath="instance/cgcut1.txt";
            data data=new data();
            data.readFile(filePath,0);
            double[][] A = centreMatrix_Creat(data);    //建立约束矩阵
            Search_XB();                  //获取基变量/第一个单位矩阵
            Init(data,A);                 //获取基本可行解中基变量的初始值b0，初始化检验数Pi
            LocalDateTime startTime = LocalDateTime.now();
            LogicLoopJudge(A);            //迭代过程
            LocalDateTime endTime = LocalDateTime.now();
            IterationTime(startTime,endTime);
        }

        /**
         *用于计算迭代时间
         * @param startTime 迭代前时间
         * @param endTime  迭代后时间
         *
         */
        private static void IterationTime(LocalDateTime startTime, LocalDateTime endTime) {
            System.out.println("迭代时间大约为:"+ ChronoUnit.MILLIS.between(startTime, endTime)+"毫秒");
        }

        private static void LogicLoopJudge(double[][] A) {
            int number = 0;
            while (true){
                int tempt = 0;
                int negativeIndex = 0;
                for (int i = 0; i < pi.length; i++) {
                    if (pi[i]<=0){
                        tempt++;  //统计检验数小于等于 0 的数量，用于判断截止迭代的条件
                    }
                    else if (pi[i]>0) {//若检验数大于0，且其在所有约束条件下的对应系数均小于等于0时
                        // 增大检验数所对应变量，不会对约束条件产生影响，且将其引入基变量后，可能会获得更大的目标函数
                        for (int j = 0;j < m;j++){
                            if (A[j][i]<=0){
                                negativeIndex++;
                            }
                        }
                        if (negativeIndex ==m){
                            System.out.println("检验数大于0，且其在所有约束条件下的对应系数均小于等于0，此线性规划问题无最优解！");
                            return;
                        }//negativeIndex 等于 m，表示当前变量对应的约束条件无法满足，即该线性规划问题无最优解，如果不满足结束条件，则开始进行一次迭代操作
                    }
                }
                if (tempt == n){//检验数均小于等于 0 ，截止条件
                    printResult(A,number);
                    break;
                }

                // 以上为判断条件编写 以下正式开始单纯形法的计算；

                System.out.println("=================开始第"+(number+1)+"次迭代================");
                int index = IntoBaseVar_Judge();                //入基索引(找到具有最大检验数的变量的索引)
                UpDataTheta(A,index);
                int index2 = OutOfBaseVar_Judge(index);         //出基索引
                RotationTransformation(A,index,index2);         //更新系数矩阵和其他相关数据，以实现从一个基本可行解到下一个基本可行解的转换。
                number++;
            }
        }

        /**
         *用于A的旋转变化，更新A
         * @param index 入基变量
         * @param index2 出基变量
         */
        private static void RotationTransformation(double[][] A,int index,int index2) {//入基、出基
            if (A[index2][index] != 1) {
                double positiveFactor = A[index2][index];
                for (int j = 0; j < n; j++) {
                    A[index2][j] /= positiveFactor; //初等行变化
                }//将入基系数改为1
                b0[index2] /= positiveFactor;
            }//利用行变换使得 A[index2][index] = 1;
            RotatingCenter(A,index,index2);
        }

        private static void RotatingCenter(double[][] A, int index, int index2) {
            for (int i = 0; i < m; i++) {//构建单位向量
                if (A[i][index]!=0 && i!=index2){
                    double factor = -A[index2][index]*A[i][index];//A[index2][index]已为1
                    double b0_factor = factor*b0[index2];
                    b0[i] += b0_factor;
                    for (int j = 0; j < n; j++) {
                        double A_factor = A[index2][j]*factor;
                        A[i][j] += A_factor;
                    }//对整行进行初等行变换
                }
            }
            initPi(A);
        }

        private static void printResult(double[][] A,int number) {
            for (int i = 0; i < m; i++) {
                var += c[basicVar[i]]*b0[i];
            }
            System.out.println("======================循环结束======================");
            System.out.println("最优值为:"+var);
            System.out.println("最优解为:");
            boolean logic = OptimalSolution();
            if (!logic){
                return;
            }
            System.out.println("基向量为:");
            for (int j : basicVar) {
                System.out.print("x" + (j + 1)+"\t");
            }
            System.out.println();
            System.out.println("迭代次数:"+number);
            System.out.println("最后一步单纯形表为:");
            printMatrix(A);
        }

        private static boolean OptimalSolution() {
            DecimalFormat sc = new DecimalFormat("0.00");//用于格式化数字，0.00表示保留两位小数
            String[] OptimalSData = new String[n];
            for (int i = 0; i < basicVar.length; i++) {
                OptimalSData[basicVar[i]] = sc.format(b0[i]);
            }//获取对应索引的值
            for (int i = 0; i < OptimalSData.length; i++) {
                if (OptimalSData[i] == null){
                    OptimalSData[i] = "0.00";
                }
            }
            System.out.println(Arrays.toString(OptimalSData));
            for (int mDatum : MData) {
                for (int j = 0; j < m; j++) {
                    if (mDatum == basicVar[j] && b0[j] != 0) {
                        System.out.println("由于最优解中存在正的人工变量，则原问题最优解可行性不佳");
                        return true;
                    }
                }
            }
            return true;
        }

        /**
         *
         * @param index 为入基索引
         * @return 返回出基索引
         * 使用的是Dantzig出基规则
         */
        private static int OutOfBaseVar_Judge(int index) {
            int index2 = 0;//对应的是数组theta的索引
            for (int i = 0; i < m; i++) {
                if (theta[index2]>theta[i]){
                    index2 = i;
                }
            }//获取最小theta所对应的索引
            basicVar[index2] = index;//将出基变量所对应的索引换成入基变量所对应索引
            return index2;
        }

        /**
         *
         * @return 返回的是入基索引
         * 使用的是Dantzig入基规则
         */
        private static int IntoBaseVar_Judge() {
            int index = 0;
            for (int i = 1; i < n; i++) {
                if (pi[index]<pi[i]){//找到的具有最大检验数的变量的索引
                    index = i;
                }
            }
            return index;
        }

        /**
         * 用于更新θ
         * @param index 入基变量
         */
        private static void UpDataTheta(double[][] A,int index) {   //theta:入基时对应的θ，选较小值
            theta = new double[m];
            for (int i = 0; i < m; i++) {
                if (A[i][index]<=0){
                    theta[i] = 1000;
                }else {
                    theta[i] = b0[i]/A[i][index];
                }
            }
        }

        /**
         * 获取第一个单位矩阵
         */
        private static void Search_XB() {
            basicVar = new int[m];
            for (int j = 0; j < m; j++) {
                basicVar[j] = n-m+j;
            }
        }
        /**
         * 数据初始化
         */
        private static void Init(data data,double[][] A) {
            for (int i = 0; i < m; i++) {      //基本可行解中基变量的初始值
                if (i<data.getAllJ().size()){
                    b0[i] = 0;
                } else if (i==data.getAllJ().size()) {
                    b0[i] = 1;
                } else {
                    int index=i-data.getAllJ().size()-1;
                    b0[i] = data.getGoalJ().get(index)[2];
                }
            }

//         初始化 目标函数对应系数c
            c = new double[n];
            for (int i = data.getSetO().size(); i < data.getSetO().size()+data.getGoalJ().size(); i++) {
                int[] list=data.getGoalJ().get(i-data.getSetO().size());
                c[i] = list[1];
            }
            // 初始检验数
            initPi(A);
        }
        /**
         *初始化检验数π
         */
        private static void initPi(double[][] A) {
            pi = new double[n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    pi[i] += c[basicVar[j]]*A[j][i];
                }
                pi[i] = c[i] -pi[i];
            }
        }//cj-sum(cB*Aji)


// 示例代码段
//        private static void Search_XB() {
//            basicVar = new int[m];
//            basicVar[0] = 2;
//            basicVar[1] = 3;
//            basicVar[2] = 4;
//            MData = new int[m];
//            MData[0] = 2;
//            MData[1] = 3;
//            MData[2] = 4;
//        }
//        private static void Init(data data,double[][] A) {
//            b0[0]=300;
//            b0[1]=400;
//            b0[2]=250;
//            c = new double[n];
//            c[0]=50;c[1]=100;
//            initPi(A);
//        }

    }

